//Returns the most likely location
//This is the function that the hunter will use, the rest are just helpers
//lastKnownLocation is merely the last city that dracula was spotted in (you're free to take a guess here)
//chancesToMove is the number of turns dracula has had opportunities to move, usually this would how long ago he was spotted
//however you can increase this number to predict even further into the future, or decrease it to find an earlier city in the trail

//possibleEndLocations has been shoehorned onto this function. It returns all the possible locations that dracula
//could be in, in order of probability (most likely first).
//When reading back possibleEndLocations, a value of -1 indicates that there are no more cities left in the array
//(ignore all cities after -1)

int draculaMostLikely(HunterView gameState, int lastKnownLocation, int chancesToMove, int possibleEndLocations[]);

//Returns the number of results
int findPathsNoRail(Connection** graph, int results[], int location);

//Returns the number of results
int appendPaths(int results[][7], int pathsToAppend[], int numPathsToAppend,int startingPos, int numTotalResults);

//Just a testing thing
void printPaths(int results[][7]);

//Figures out the most common destination
int bucketSortMostCommon (int results[][7]);

//Same as above but returns a sorted array into the second parameter

void bucketSortArray (int results[][7], int sortedArray[]);

//Removes a path with hides or double backs
void removeHides(int results[]);

//Compares a sorted list of locations dracula could lie in, with a list of possible moves that can be made
//Returns a city if there is a match, returns -1 otherwise.
int compareLists(int sortedLocations[], int possibleMoves[]);


int draculaMostLikely(HunterView gameState, int lastKnownLocation, int chancesToMove, int possibleEndLocations[]){

        int possibleMoves[1000][7] = {{0}};
        int tempResults[15] = {0};
        int numTempResults = 0;
        int numTotalResults = 1;
        int currentPosition = 0;
        int depth = 0;
        int retval = 0;
        int counter = 0;
        
        //Declare adjacency matrix
    Connection **graph = malloc(sizeof(Connection*)*(SEA_END+1));
    int i, j;
    for (i = 0; i <= SEA_END; i++){
        graph[i] = malloc(sizeof(Connection)*(SEA_END+1));
        for (j = 0; j <= SEA_END; j++){
            graph[i][j] = malloc(sizeof(struct connection));
        }
    }
    //-----------------------
        giveGraph (gameState, graph);
        
        possibleMoves[0][0] = 1;
        possibleMoves[0][1] = lastKnownLocation;
        
        
        while (depth < chancesToMove) {
        //Check depth
                if (possibleMoves[currentPosition+1][0] > depth) {
                        depth++;
                }
                numTempResults = findPathsNoRail(graph, tempResults, possibleMoves[currentPosition][possibleMoves[currentPosition][0]]);
                numTotalResults = appendPaths(possibleMoves, tempResults, numTempResults, currentPosition, numTotalResults);
                currentPosition++;
        }
        

        
        while (counter < numTotalResults) {
                removeHides(possibleMoves[counter]);
                counter++;
        }
        
        bucketSortArray (possibleMoves, possibleEndLocations);
        
        retval = bucketSortMostCommon(possibleMoves);
        
        return retval;
}

int findPathsNoRail(Connection** graph, int results[], int location){
        int graphCounter = 0;
        int resultsCounter = 0;
        while (graphCounter < SEA_END + 1) {
                
                if (graph[location][graphCounter]->sea == 1){
                        results[resultsCounter] = graphCounter;
                        resultsCounter++;
                }
                if (graph[location][graphCounter]->road == 1){
                        results[resultsCounter] = graphCounter;
                        resultsCounter++;
                }
                graphCounter++;
        }
        return resultsCounter;
}

int appendPaths(int results[][7], int pathsToAppend[], int numPathsToAppend, int startingPos, int numTotalResults){
        //Copy the startingPos, numPathsToAppend times and place at numTotalResults
        
        
        
        int pathCounter = 0;
        int posCounter = 1;
        while (pathCounter < numPathsToAppend) {
                while (posCounter <= results[startingPos][0]){
                        results[numTotalResults + pathCounter][posCounter] = results[startingPos][posCounter];
                        posCounter++;
                }
                //Append the digits and adjust path lengths
                results[numTotalResults + pathCounter][posCounter] = pathsToAppend[pathCounter];
                results[numTotalResults + pathCounter][0] = results[startingPos][0] + 1;
                posCounter = 1;
                pathCounter++;
        }
                
        return numTotalResults + numPathsToAppend;
}

void printPaths(int results[][7]){
        int counter = 0;
        int depthCounter = 1;
        while (counter < 1000) {
                if (results[counter][0] != 0) {
                        printf("(%d)   ", results[counter][0] );
                        while (depthCounter <= results[counter][0]){
                                printf("%d->", results[counter][depthCounter] );
                                depthCounter++;
                        }
                        depthCounter = 1;
                        printf("\n");
                }
                counter++;
        }
}

int bucketSortMostCommon(int results[][7]){
        int buckets[SEA_END+1] = {0};
        int counter = 0;
        int highestVal = 0;
        int highestIndex = 0;
        
        while (counter < SEA_END+1) {
                if (results[counter][0] != 0) {
                        buckets[results[counter][results[counter][0]]]++;
                }
                counter++;
        }
        counter = 0;
        
        while (counter < SEA_END+1){
                if (buckets[counter] > highestVal) {
                        highestIndex = counter;
                        highestVal = buckets[counter];
                }
                counter++;
        }
        return highestIndex;
}

void removeHides(int results[]){
        int counter = 1;
        int buckets[SEA_END+1] = {0};
        
        while (counter < results[0]+1){
                buckets[results[counter]]++;
                counter++;
        }
        counter = 0;
        while (counter < SEA_END) {
                if (buckets[counter] > 1){
                        results[0] = 0;
                }
                counter++;
        }
}

//Same as above but returns a sorted array into the second parameter
void bucketSortArray (int results[][7], int sortedArray[]){
	int buckets[SEA_END+1] = {0};
	int counter = 0;
	int sortedCounter = 0;
	int highestVal = 0;
    int highestIndex = 0;
	
	while (counter < SEA_END+1) {
		if (results[counter][0] != 0) {
			buckets[results[counter][results[counter][0]]]++;
		}
		counter++;
	}
	
	while (sortedCounter < SEA_END+1){
		counter = 0;
		while (counter < SEA_END+1) {
			highestVal = 0;
			highestIndex = 0;
			if (buckets[counter] > highestVal) {
				highestIndex = counter;
				highestVal = buckets[counter];
			}
			counter++;
		}
		if (counter != SEA_END+1){
			sortedArray[sortedCounter] = highestIndex;
			buckets[highestIndex] = 0;
			sortedCounter++;
		} else {
			sortedArray[sortedCounter] = -1;
			sortedCounter = SEA_END+1;
		}
	}
	
}

int compareLists(int sortedLocations[], int possibleMoves[]){
	int sortedCounter = 0;
	int possibleCounter = 0;
	int retval = -1;
	
	while (sortedLocations[sortedCounter] != -1){
		while (possibleCounter < possibleMoves[0]){
			if (sortedLocations[sortedCounter] == possibleMoves[possibleCounter+1]){
				retval = sortedLocations[sortedCounter];
				possibleCounter = possibleMoves[0];
				sortedCounter = -2;
			}
			possibleCounter++;
		}
		sortedCounter++;
	}
	
	return retval;

}


